1. Field of the Invention
This invention relates to an error correction coding/decoding method and circuit, and more specifically, to a method of coding/decoding Reed-Solomon codes formed of symbols larger than information symbols when data is transmitted such as in data transfer and data recording, and a circuit for implementing this method.
2. Description of Related Art
Error correction coding is often used when digital information is transmitted. "Code Theorem" edited by the Institute of Electronic Information Communication (Denshi Joho Tsushin Gakkairon), written by Hideo Imai, first edition published on Mar. 15, 1990, various error correction coding and decoding techniques are disclosed. One of these is Reed-Solomon coding, a method which performs symbol error correction on a symbol of 8 bits, which has high compatibility with computers or digital instruments, and which is therefore widely used for information transfer or recording.
Flash memories, which in addition to permitting write erase can store data even without power and achieve higher levels of Integration than DRAM, are now attracting interest, and it is hoped to use them as memory devices. However flash memories suffer from the disadvantage that when a large number of writes and erasures are performed, internal cells are damaged and data can be destroyed. Error correction is therefore often used when data is recorded on flash memories. Further when data is erased, all data becomes "1", so this is used to verify the erasure.
In general, when data is recorded on a disk memory, 512 bytes of information data are stored as one sector. Also as memories store data in units of 8 bits, a Reed-Solomon code is used whereof 8 bits comprise one symbol. However in such a Reed-Solomon code wherein 8 bits comprise one symbol, the coding length is generally limited to 255, and consequently the data has to be split into a plurality of code words.
Alternatively, for example, data may be protected by a Reed-Solomon code wherein one symbol is 10 bits. In this case it is generally possible to have a coding length of up to 1023 symbols, so 1 sector of data is one code word.
FIG. 15 shows a typical code structure of a conventional error correction coding and decoding method, and in particular a (418, 410) Reed-Solomon code.
Herein, "418" is the code symbol length and "410" is the information length. Four symbols can be corrected. In FIG. 15, 30 is a removed part, 31 is a real information data symbol part, 32 is a check symbol part and 36 is a dummy symbol part.
The Reed-Solomon code shown in FIG. 15 actually has a length of 1023 symbols, but it is coded assuming that the 605 symbols of the removed part 30 are 0. Further if 1 sector is 512 bytes, there will be 4096 bits, i.e. 4 bits short of the number necessary to assign 10 bits/symbol. The 4 bit dummy symbol 36 is therefore added, and with a real information data symbol part 31 of 410 symbols, 8 symbols of 10 bits are generated for the check symbol part 32.
Next, a coding circuit for generating check bytes in the Reed-Solomon code of FIG. 15 will be described with reference to FIG. 16. Herein, data input and output of check symbols are handled in 8 bit units so that these operations can be normally performed by a flash memory. In FIG. 16, 22 is an 8 bit information data input terminal, 19 is a 8 bit/10 bit conversion circuit, 23 is a coding circuit for Reed-Solomon codes on a OF (2E10), 26 is a 8 bit check symbol output terminal, and 29 is a 10 bit/8 bit conversion circuit.
The operation of the structure in FIG. 16 will be described. Check symbols of the Reed-Solomon code are first generated in the coding circuit 23, for which purpose the circuit 23 is first cleared to "0".
First, 8 bit information data is input from an information data input terminal 22, and then input to the 8 bit/10 bit conversion circuit 19. When 10 bit information has accumulated in the 8 bit/10 bit conversion circuit 19, this information is input to the coding circuit 23.
When the entire real information data symbol part 31 is input to the coding circuit 23 including the 4 bits of the dummy symbol part 36 in FIG. 15, the 8 symbol (80 bit) check symbol part 32 is obtained. This means there is no need to calculate the removed contribution of the code part 30.
The check symbol part 32 is subjected to a 10 bit/8 bit conversion by a 10 bit/8 bit conversion circuit from the top down, and check byte data is output from the check symbol output terminal 26 every 8 bits. In other words, 10 byte data is output as check symbols.
Next, a conventional decoding method and in particular a syndrome calculation will be described with reference to FIG. 17. The construction of FIG. 17 assumes a flash memory having also a data erasure check function. In FIG. 17, 1 is a data input terminal for inputting 8 bit received data, 5 is a Galois field summing circuit on a GF (2E10), 7 is a 10 bit register, 8 is a Galois field coefficient multiplying circuit on a GF (2E10), 9 is a syndrome output terminal, 20 is a FF check circuit for checking whether or not all 8 bit data is "1", i.e. whether or not it is "FF" in terms of HEX code, and 21 is an erasure check flag output terminal.
First, error correction decoding is performed, it being assumed that the register 7 is first cleared to 0. Received data input from the data input terminal 1 is input to the 8 bit/10 bit conversion circuit 19. When 10 bit data has accumulated in the 8 bit/10 bit conversion circuit 19, a Galois field summation is performed on this information and the output of the Galois field coefficient multiplying circuit 8 in the Galois field summing circuit 5. The summation result is input to the register 7. The output of the register 7 is transmitted to the input terminal of the Galois field coefficient multiplying circuit 8.
The state of the register 7 when all of the real information data symbol part 31 and check symbol part 32 has been input, is the syndrome Sj, and this is output from the syndrome output terminal 9.
At that time, even if a slip of symbol units should occur when the leading data symbol of the Reed-Solomon code is "0", there is still a possibility that error correction decoding will take place with the slip still present as Reed-Solomon codes are cyclic codes.
On the other hand when data is erased in a flash memory, all data becomes "1", but it is necessary to verify whether or not the erasure has been performed without any errors.
In this case, 8 bit data is input to the FF check circuit 20 from the data input terminal 1, and if "0" is detected in even one bit, an error flag is output by the erasure check flag output terminal 21.
Now conventionally, when error correction is performed, decoding of codes formed from product codes is performed after first storing them in a memory. FIG. 18 is a block diagram of a circuit showing an example of such a case. In the figure, 59 is a buffer memory, 60 is a syndrome circuit, 63 is an error position/magnitude detecting circuit which determines error position and magnitude, 64 is a correction circuit, and 65 is a post-correction decoded data output terminal.
In the above construction, coded data input from the data input terminal 1 is stored in the buffer memory 59. Subsequently interleaving is undone, the data is converted to a coded sequence and input to the syndrome circuit 60. Based on the syndrome thereby obtained, error positions and magnitudes are determined by the error position/magnitude detecting circuit 63, error position data in the buffer memory 59 is read by the correction circuit 64, the errors are corrected, and the data is written to the buffer memory 59. In the case of product codes, this decoding operation is repeated a plurality of times, and all data is decoded and output by the decoded data output terminal 65.
When the aforesaid operations are performed by one buffer memory, input of received data, output to the syndrome circuit, input/output of error position data and output of corrected data must be performed by time division. In particular, when decoding is repeated a plurality of times as with product codes, a buffer memory having high speed access must be used.
To ensure reliability of the memory, 1 bit error correction and 2 bit error detection are often used, a typical example being the (72, 64) binary linear code. Herein, "72" is the bit coding length and "64" is the bit information length, i.e. there are 8 check bits.
In such a decoding circuit, all coded bit data is often decoded in parallel, and there is often another circuit to detect errors. This type of code is described for example in "Fault Tolerance Systems" (Edited by the Institute of Electronics Information Communications of Japan (Denshi Joho Tsushin Gakkai) by Yoshihiro Toma, first edition published on Jun. 10, 1990).
FIG. 19 is a block diagram of a conventional decoding circuit for (72, 64) binary linear codes. In the figure, 66 is an 8 bit input OR circuit to which signals from the syndrome circuit 60 are input, 67 is a 72 bit input NOR circuit to which signals from the error position/magnitude detecting circuit 63 are input, 68 is a 2 bit AND circuit to which the outputs of the 8 bit input OR circuit 66 and 72 bit input NOR circuit are supplied, and 49 is a correction impossibility detection flag output terminal for outputting a correction impossibility detection flag from the 2 input AND circuit 68.
In the aforesaid construction when memory error correction is performed, as the data path has a parallel construction, 72 bit coded data is first input to the syndrome circuit 60. In the syndrome circuit 60, an 8 bit syndrome is generated from received data and output. The error position/magnitude detecting circuit 63 checks whether or not an 8 bit pattern of bit positions comprising a check bit determined by a parity check matrix is identical with the syndrome. The result is sent to the 72 bit input NOR circuit 67 and correction circuit 63, and at that time, 64 bits of an information part are sent to the correction circuit 64. The correction circuit performs an XOR operation on the received information bits and the error detection result of each bit, and the result is output from the decoded data output terminal 65.
In this coding, error detection is performed on 2 bit errors. This means that if the syndrome is not "0" and it is not identical to a correctable pattern of a parity check matrix of 72 bits coding length, correction is impossible and an error is detected. The 8 bit input OR circuit 66 checks that the 8 bits of the syndrome are not "0", the 72 bit input NOR circuit 67 checks whether the error is not a 1 bit error, and 2 bit AND circuit 68 calculates the logical product of these two check results which logical product is output from the correction impossibility detection flag output terminal 49.
The aforesaid construction and operation are also described for example in Japanese Patent Publication Sho 53-5099 (applied for by D. W. Price, Nov. 8, 1972).
Problems Which This Invention Attempts to Solve
As the conventional error correction coding/decoding method has the construction described hereinabove, it leaves a large number of problems as described hereinbelow.
The first problem is that if a 1 symbol per 10 bit Reed-Solomon code is used for 8 bit input/output data, an 8 bit/10 bit conversion circuit and a 10 bit/D bit conversion circuit are necessary, symbol clocks must be generated both for 8 bits and 10 bits, and a bit clock is required.
The second problem is that a special circuit is required to check whether data is all "1" to verify erasure of a flash memory.
The third problem is that even when a slip occurs in an Reed-Solomon code in symbol units, correction decoding may leave the slip unchanged since the Reed-Solomon code is cyclic.
The fourth problem is that when coded data is stored in a memory, since input of received data, input/output to the decoding circuit and output of the decoded result are performed on a time division basis, a high speed access memory is required in order to perform a plurality of decoding operations.
The fifth problem is that, to output an error correction impossibility flag in a (72, 64) binary linear code used for memory error correction, it is necessary to perform a 1 bit error check in 72 bits, and this requires a circuit to perform a logical computation on the result. This makes a long delay time inevitable, and requires a circuit with a large number of gates to perform the computation.
This invention was conceived to overcome the aforesaid problems inherent in the prior art. It aims to provide an error correction method and circuit which performs error correction, coding and decoding by means of a simple structure with very high reliability by handling only 8 bit symbols and eliminating redundant circuits.